/**
 * 统计一个数字在排序数组中出现的次数。
 *思路：二分查找： 搜索左边界和右边界
 * 关于二分详细解说：https://labuladong.gitee.io/algo/2/20/29/
 */
class Search {
    public int search(int[] nums, int target) {
        int a=binaryLeft(nums,0,nums.length,target);
        int b=binaryRight(nums,0,nums.length,target);
      if(a==-1&&b==-1) {
          return 0;
      } else {
          return b-a+1;
      }
    }
     public int binaryLeft(int[] nums,int left,int right,int target) {
        while(left<right) {//左闭右开区间
            int mid=left+((right-left)>>>1);
            if(nums[mid]<target) {
                left=mid+1;//左闭，所以要mid+1,因为left有取到
            } else if(nums[mid]>target) {
                right=mid;//右开，所以要=mid,因为righ没有取到
            } else {
                right=mid;//缩小右边界，确定target的左边界
            }
        }
        if(left==nums.length) {//判断索引是否越界
            return -1;
        }
        return nums[left]==target?left:-1;//查看有没有这个数
    }
    public int binaryRight(int[] nums,int left,int right,int target) {
        while(left<right) {//左闭右开区间
            int mid=left+((right-left)>>>1);
            if(nums[mid]<target) {
                left=mid+1;//左闭，所以要mid+1,因为left有取到
            } else if(nums[mid]>target) {
                right=mid;//右开，所以要=mid,因为righ没有取到
            } else {
                left=mid+1;//缩小左边界，确定target的右边界
            }
        }
        if(left-1<0) {//判断索引是否越界
            return -1;
        }
        return nums[left-1]==target?left-1:-1;//查看有没有这个数
    }
}